package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 1/13/21 9:54 AM
 *
 *  https://leetcode-cn.com/problems/merge-k-sorted-lists/
 *
 *  n:平均每个链表度长度
 *  k: 链表个数
 *  时间复杂度: O(nklogk)
 *  空间复杂的: O(k)
 */
public class _23_合并K个升序链表_归并 {

    public ListNode mergeKLists(ListNode[] lists) {

//        dummy

        if (lists == null || lists.length == 0) {

            return null;
        }

        if (lists.length == 1) {
            return lists[0];
        }


        return divide(lists,0,lists.length - 1);
    }

    private ListNode divide(ListNode[] lists, int hIndex, int eIndex) {

        if (hIndex == eIndex) {

            return lists[hIndex];
        }

        int mid = hIndex + ((eIndex - hIndex) >> 1);

        ListNode h1 = divide(lists, hIndex, mid);
        ListNode h2 = divide(lists, mid + 1, eIndex);


        return merge(h1,h2);
    }


    private ListNode merge(ListNode h1, ListNode h2) {

        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;

        while (h1 != null) {


            if (h2 != null && h1.val >= h2.val) {

                tail.next = h2;
                tail = h2;
                h2 = h2.next;
            }else {

                tail.next = h1;
                tail = h1;
                h1 = h1.next;
            }
        }

        if (h2 != null) {

            tail.next = h2;
        }


        return dummyHead.next;
    }

}
